package com.freedy.dataStructure.tree;

import java.util.StringJoiner;

/**
 * 平衡二叉树
 *
 * @author Freedy
 * @date 2021/4/2 22:47
 */
public class AVLTree {
    private Node root;

    AVLTree(Integer rootVal) {
        root = new Node(rootVal);
    }

    public void changeRootVal(int val) {
        root.setData(val);
    }

    public void add(Integer val) {
        if (val != null) {
            Node node = new Node(val);
            root.add(node);
        }
    }

    public void print(TreeEnum mode) {
        switch (mode) {
            case preOrder -> root.preOrder();
            case infixOrder -> root.infixOrder();
            case postOrder -> root.postOrder();
            default -> throw new RuntimeException("参数不正确");
        }
    }

    public int height(TreeEnum mode) {
        int height;
        switch (mode) {
            case height -> height = root.height();
            case leftHeight -> height = root.leftHeight();
            case rightHeight -> height = root.rightHeight();
            default -> throw new RuntimeException("参数不正确");
        }
        return height;
    }

    public boolean del(int val) {
        Node target = root.search(val);
        if (target == null) return false;
        Node parent = root.searchParent(val);
        if (parent == null) {
            //表示要删除的是根节点
            if (target.getLeftNode() == null && target.getRightNode() == null) {
                //表示该树只有一个节点且是根节点，这是不能让其删除
                throw new RuntimeException("binary sort tree can not be empty");
            } else if (target.getLeftNode() == null && target.getRightNode() != null) {
                //要删除的节点只有右子树
                root = root.getRightNode();
                return true;
            } else if (target.getLeftNode() != null && target.getRightNode() == null) {
                //要删除的节点只有左子树
                root = root.getLeftNode();
                return true;
            } else if (target.getLeftNode() != null && target.getRightNode() != null) {
                //要删除的节点是有两个子树
                int minVal = delMinVal(target.getRightNode());
                target.setData(minVal);
                return true;
            }
        } else {
            if (target.getLeftNode() == null && target.getRightNode() == null) {
                //表示要删除的节点是叶子节点
                if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) {
                    parent.setLeftNode(null);
                    return true;
                } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) {
                    parent.setRightNode(null);
                    return true;
                }
            } else if (target.getLeftNode() == null && target.getRightNode() != null) {
                //要删除的节点只有右子树
                if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) {
                    //要删的节点在parent的左子树
                    parent.setLeftNode(target.getRightNode());
                    return true;
                } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) {
                    //要删的节点在parent的右子树
                    parent.setRightNode(target.getRightNode());
                    return true;
                }
            } else if (target.getLeftNode() != null && target.getRightNode() == null) {
                //要删除的节点只有左子树
                if (parent.getLeftNode() != null && parent.getLeftNode().getData() == val) {
                    //要删的节点在parent的左子树
                    parent.setLeftNode(target.getLeftNode());
                    return true;
                } else if (parent.getRightNode() != null && parent.getRightNode().getData() == val) {
                    //要删的节点在parent的右子树
                    parent.setRightNode(target.getLeftNode());
                    return true;
                }
            } else if (target.getLeftNode() != null && target.getRightNode() != null) {
                //要删除的节点是有两个子树
                int minVal = delMinVal(target.getRightNode());
                target.setData(minVal);
                return true;
            }
        }
        throw new RuntimeException("删除失败");
    }

    /**
     * 找到排序二叉树中最小的值，并删除
     */
    private int delMinVal(Node node) {
        Node pre = null;
        while (node.getLeftNode() != null) {
            pre = node;
            node = node.getLeftNode();
        }
        Integer val = node.getData();
        if (pre != null) {
            pre.setLeftNode(null);
        } else {
            //表示node没有子节点，直接删除自己
            Node parent = root.searchParent(val);
            if (parent.getLeftNode() != null && parent.getLeftNode().getData().equals(val)) {
                parent.setLeftNode(node.getRightNode());
            } else if (parent.getRightNode() != null && parent.getRightNode().getData().equals(val)) {
                parent.setRightNode(node.getRightNode());
            }
        }
        return val;
    }

    private static class Node {
        private Integer data;
        private Node leftNode;
        private Node rightNode;

        //*******************************CONSTRUCT**********************************
        public Node() {
        }

        public Node(Integer data) {
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public Node getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node leftNode) {
            this.leftNode = leftNode;
        }

        public Node getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node rightNode) {
            this.rightNode = rightNode;
        }

        @Override
        public String toString() {
            return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                    .add("data=" + data)
                    .add("leftNode=" + (leftNode == null ? "" : leftNode.hashCode()))
                    .add("rightNode=" + (rightNode == null ? "" : rightNode.hashCode()))
                    .toString();
        }
        //***********************************END***************************************

        /**
         * @return 返回当前节点下面的树的高度
         */
        public int height() {
            return Math.max(leftNode == null ? 0 : leftNode.height(),
                    rightNode == null ? 0 : rightNode.height()) + 1;
        }

        public int leftHeight() {
            if (leftNode == null) return 0;
            return leftNode.height();
        }

        public int rightHeight() {
            if (rightNode == null) return 0;
            return rightNode.height();
        }

        /**
         * 左旋转
         */
        public void leftRotate() {
            //创建新的节点
            Node node = new Node(data);
            //讲新的节点的左子树设置为当前节点的左子树
            node.setLeftNode(this.getLeftNode());
            //把新的节点的右子树设置为当前节点的*右子树的左子树*
            node.setRightNode(this.getRightNode().getLeftNode());
            //把当前节点换成右子节点的值
            this.setData(this.getRightNode().getData());
            //把当前节点的右子树设置为当前节点的右子树的右子树
            this.setRightNode(this.getRightNode().getRightNode());
            //把当前节点的左子树设置为新的节点
            this.setLeftNode(node);
        }

        /**
         * 右旋转
         */
        public void rightRotate(){
            Node node = new Node(data);
            node.setLeftNode(this.getLeftNode().getRightNode());
            node.setRightNode(this.getRightNode());
            this.setData(this.getLeftNode().getData());
            this.setRightNode(node);
            this.setLeftNode(this.getLeftNode().getLeftNode());
        }

        /**
         * 添加节点
         * 递归的形式添加节点，注意需要满足的二叉排序树的要求
         */
        public void add(Node node) {
            if (node == null) return;
            if (node.getData() < this.getData()) {
                //向左边比较
                if (this.getLeftNode() == null) {
                    //无节点 直接添加
                    this.setLeftNode(node);
                } else {
                    //有节点 递归添加
                    this.getLeftNode().add(node);
                }
            } else {
                //向右边比较
                if (this.getRightNode() == null) {
                    //无节点 直接添加
                    this.setRightNode(node);
                } else {
                    //有节点 递归添加
                    this.getRightNode().add(node);
                }
            }
            //当添加完一个节点后，如果 右子树的高度-左子树的高度>1,即右边比左边高所以要左旋转
            if (this.rightHeight() - this.leftHeight() > 1) {
                if (this.getRightNode()!=null&&this.getRightNode().leftHeight()>this.getRightNode().rightHeight()){
                    this.getRightNode().rightRotate();
                }
                leftRotate();
                return;
            }
            //当添加完一个节点后，如果 左子树的高度-右子树的高度>1,即左边比右边高所以要右旋转
            if(this.leftHeight()-this.rightHeight()>1){
                //若果左子树的右子树的高度大于左子树的左子树的高度
                if (this.getLeftNode()!=null&&this.getLeftNode().rightHeight()>this.getLeftNode().leftHeight()){
                    this.getLeftNode().leftRotate();
                }
                rightRotate();
            }
        }

        /**
         * 查找结点
         *
         * @param val 要查找节点的值
         * @return 节点
         */
        public Node search(int val) {
            if (val == this.data) {
                //找到就直接返回
                return this;
            } else if (val < this.data) {
                //若果小于就去左节点继续查找
                if (this.getLeftNode() != null) {
                    return this.getLeftNode().search(val);
                }
            } else {
                //若果大于就去右节点继续查找
                if (this.getRightNode() != null) {
                    return this.getRightNode().search(val);
                }
            }
            return null;
        }

        /**
         * 返回要查找节点的父节点
         */
        public Node searchParent(int val) {
            if (this.getLeftNode() != null && this.getLeftNode().getData() == val ||
                    this.getRightNode() != null && this.getRightNode().getData() == val) {
                //找到其父节点
                return this;
            } else {
                if (this.getData() > val) {
                    //若果小于就去左节点继续查找
                    if (this.getLeftNode() != null) {
                        return this.getLeftNode().searchParent(val);
                    }
                } else {
                    //若果大于就去右节点继续查找
                    if (this.getRightNode() != null) {
                        return this.getRightNode().searchParent(val);
                    }
                }
                return null;
            }
        }

        /**
         * 前中后序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (leftNode != null) {
                leftNode.preOrder();
            }
            if (rightNode != null) {
                rightNode.preOrder();
            }
        }

        public void infixOrder() {
            if (leftNode != null) {
                leftNode.infixOrder();
            }
            System.out.println(this);
            if (rightNode != null) {
                rightNode.infixOrder();
            }
        }

        public void postOrder() {
            if (leftNode != null) {
                leftNode.postOrder();
            }
            if (rightNode != null) {
                rightNode.postOrder();
            }
            System.out.println(this);
        }

    }
}
